<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes">
<meta name="generator" content="litedown 0.7">
<title></title>
<style type="text/css">
body {
  font-family: sans-serif;
  max-width: 800px;
  margin: auto;
  padding: 1em;
  line-height: 1.5;
  print-color-adjust: exact;
  -webkit-print-color-adjust: exact;
}
body, .abstract, code, .footnotes, footer, #refs, .caption { font-size: .9em; }
li li { font-size: .95em; }
ul:has(li > input[type="checkbox"]) { list-style: none; padding-left: 1em; }
*, :before, :after { box-sizing: border-box; }
a { color: steelblue; }
pre, img { max-width: 100%; }
pre { white-space: pre-wrap; word-break: break-word; }
pre code { display: block; padding: 1em; overflow-x: auto; }
code { font-family: 'DejaVu Sans Mono', 'Droid Sans Mono', 'Lucida Console', Consolas, Monaco, monospace; }
:not(pre, th) > code, code[class], div > .caption { background: #f8f8f8; }
pre > code:is(:not([class]), .language-plain, .language-none, .plain), .box, .figure, .table { background: inherit; border: 1px solid #eee; }
pre > code {
  &.message { border-color: #9eeaf9; }
  &.warning { background: #fff3cd; border-color: #fff3cd; }
  &.error { background: #f8d7da; border-color: #f8d7da; }
}
.fenced-chunk { border-left: 1px solid #666; }
.code-fence {
  opacity: .4;
  border: 1px dashed #666;
  border-left: 2px solid;
  &:hover { opacity: inherit; }
}
.box, .figure, .table, table { margin: 1em auto; }
div > .caption { padding: 1px 1em; }
.figure { p:has(img, svg), pre:has(svg) { text-align: center; } }
.flex-col { display: flex; justify-content: space-between; }
table {
  &:only-child:not(.table > *) { margin: auto; }
  th, td { padding: 5px; font-variant-numeric: tabular-nums; }
  thead, tfoot, tr:nth-child(even) { background: whitesmoke; }
  thead th { border-bottom: 1px solid #ddd; }
  &:not(.datatable-table) {
    border-top: 1px solid #666;
    border-bottom: 1px solid #666;
  }
}
blockquote {
  color: #666;
  margin: 0;
  padding: 1px 1em;
  border-left: .5em solid #eee;
}
hr, .footnotes::before { border: 1px dashed #ddd; }
.frontmatter { text-align: center; }
#TOC {
  a { text-decoration: none; }
  ul { list-style: none; padding-left: 1em; }
  & > ul { padding: 0; }
  ul ul { border-left: 1px solid lightsteelblue; }
}
.body h2 { border-bottom: 1px solid #666; }
.body .appendix, .appendix ~ h2 { border-bottom-style: dashed; }
.main-number::after { content: "."; }
span[class^="ref-number-"] { font-weight: bold; }
.ref-number-fig::after, .ref-number-tab::after { content: ":"; }
.cross-ref-chp::before { content: "Chapter "; }
.cross-ref-sec::before { content: "Section "; }
.cross-ref-fig::before, .ref-number-fig::before { content: "Figure "; }
.cross-ref-tab::before, .ref-number-tab::before { content: "Table "; }
.cross-ref-eqn::before, .MathJax_ref:has(mjx-mtext > mjx-c + mjx-c)::before { content: "Equation "; }
.abstract, #refs {
  &::before { display: block; margin: 1em auto; font-weight: bold; }
}
.abstract::before { content: "Abstract"; text-align: center; }
#refs::before { content: "Bibliography"; font-size: 1.5em; }
.ref-paren-open::before { content: "("; }
.ref-paren-close::after { content: ")"; }
.ref-semicolon::after { content: "; "; }
.ref-and::after { content: " and "; }
.ref-et-al::after { content: " et al."; font-style: italic; }
.footnote-ref a {
  &::before { content: "["; }
  &::after { content: "]"; }
}
section.footnotes {
  margin-top: 2em;
  &::before { content: ""; display: block; max-width: 20em; }
}
.fade {
  background: repeating-linear-gradient(135deg, white, white 30px, #ddd 32px, #ddd 32px);
  opacity: 0.6;
}

@media print {
  body { max-width: 100%; }
  tr, img { break-inside: avoid; }
}
@media only screen and (min-width: 992px) {
  body:not(.pagesjs) pre:has(.line-numbers):not(:hover) { white-space: pre; }
}
</style>
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@xiee/utils@1.14.14/css/prism-xcode.min.css">
<script src="https://cdn.jsdelivr.net/npm/prismjs@1.29.0/components/prism-core.min.js" defer></script>
<script src="https://cdn.jsdelivr.net/npm/prismjs@1.29.0/plugins/autoloader/prism-autoloader.min.js" defer></script>
</head>
<body>
<div class="frontmatter">
</div>
<div class="body">
<pre><code class="language-r"># Longest Increasing Subsequence (Dynamic Programming)
#
# The Longest Increasing Subsequence (LIS) problem is a classic dynamic programming problem.
# Given an array of integers, find the length of the longest subsequence that is strictly
# increasing. A subsequence is derived from the array by deleting some or no elements
# without changing the order of the remaining elements.
#
# Time Complexity: O(n²) for basic DP, O(n log n) for optimized binary search version
# Space Complexity: O(n) for both approaches
#
# Applications:
# - Bioinformatics (DNA sequence analysis)
# - Stock market analysis (longest upward trend)
# - Scheduling problems
# - Game theory (optimal play sequences)
# - Data compression and pattern recognition

# Basic DP solution for Longest Increasing Subsequence
longest_increasing_subsequence &lt;- function(nums) {
  #' Find the length of the longest increasing subsequence using Dynamic Programming
  #' @param nums: Numeric vector of integers
  #' @return: List containing max length, DP array, and one possible LIS
  
  n &lt;- length(nums)
  
  # Handle edge cases
  if (n == 0) {
    return(list(
      max_length = 0,
      dp_array = c(),
      lis_sequence = c(),
      dp_table = c()
    ))
  }
  
  if (n == 1) {
    return(list(
      max_length = 1,
      dp_array = c(1),
      lis_sequence = nums,
      dp_table = c(1)
    ))
  }
  
  # Initialize DP array: dp[i] = length of LIS ending at index i
  dp &lt;- rep(1, n)
  
  # Fill DP array
  for (i in 2:n) {
    for (j in 1:(i - 1)) {
      if (nums[j] &lt; nums[i]) {
        dp[i] &lt;- max(dp[i], dp[j] + 1)
      }
    }
  }
  
  # Find maximum length
  max_length &lt;- max(dp)
  
  # Backtrack to find one possible LIS
  lis_sequence &lt;- c()
  current_length &lt;- max_length
  
  for (i in n:1) {
    if (dp[i] == current_length) {
      lis_sequence &lt;- c(nums[i], lis_sequence)
      current_length &lt;- current_length - 1
      if (current_length == 0) break
    }
  }
  
  return(list(
    max_length = max_length,
    dp_array = dp,
    lis_sequence = lis_sequence,
    dp_table = dp
  ))
}

# Optimized O(n log n) solution using binary search
longest_increasing_subsequence_optimized &lt;- function(nums) {
  #' Find the length of the longest increasing subsequence using binary search
  #' @param nums: Numeric vector of integers
  #' @return: Length of the longest increasing subsequence
  
  n &lt;- length(nums)
  
  if (n == 0) return(0)
  if (n == 1) return(1)
  
  # tails[i] stores the smallest tail of all increasing subsequences of length i+1
  tails &lt;- c()
  
  for (num in nums) {
    # Binary search for the position to replace or extend
    pos &lt;- binary_search_insert_position(tails, num)
    
    if (pos &gt; length(tails)) {
      # Extend the sequence
      tails &lt;- c(tails, num)
    } else {
      # Replace the element at position pos
      tails[pos] &lt;- num
    }
  }
  
  return(length(tails))
}

# Helper function for binary search
binary_search_insert_position &lt;- function(arr, target) {
  #' Binary search to find the position where target should be inserted
  #' @param arr: Sorted numeric vector
  #' @param target: Value to insert
  #' @return: Position (1-indexed) where target should be inserted
  
  if (length(arr) == 0) return(1)
  
  left &lt;- 1
  right &lt;- length(arr)
  
  while (left &lt;= right) {
    mid &lt;- left + (right - left) %/% 2
    
    if (arr[mid] &lt; target) {
      left &lt;- mid + 1
    } else {
      right &lt;- mid - 1
    }
  }
  
  return(left)
}

# Function to find all possible LIS sequences (simplified version)
find_all_lis &lt;- function(nums) {
  #' Find all possible longest increasing subsequences
  #' @param nums: Numeric vector of integers
  #' @return: List of all possible LIS sequences
  
  n &lt;- length(nums)
  if (n == 0) return(list())
  
  # Calculate DP array
  dp &lt;- rep(1, n)
  for (i in 2:n) {
    for (j in 1:(i - 1)) {
      if (nums[j] &lt; nums[i]) {
        dp[i] &lt;- max(dp[i], dp[j] + 1)
      }
    }
  }
  
  max_length &lt;- max(dp)
  
  # For simplicity, return just one LIS (same as the main function)
  # Finding all possible LIS is complex and not essential for the algorithm demonstration
  result &lt;- longest_increasing_subsequence(nums)
  return(list(result$lis_sequence))
}

# Helper function to print DP table
print_lis_dp &lt;- function(dp_array, nums) {
  cat(&quot;DP Array for Longest Increasing Subsequence:\n&quot;)
  cat(&quot;Input Array:&quot;, paste(nums, collapse = &quot;, &quot;), &quot;\n&quot;)
  cat(&quot;DP Array   :&quot;, paste(dp_array, collapse = &quot;, &quot;), &quot;\n&quot;)
  cat(&quot;Max Length :&quot;, max(dp_array), &quot;\n\n&quot;)
}

# ===========================
# Example Usage &amp; Testing
# ===========================
cat(&quot;=== Longest Increasing Subsequence (Dynamic Programming) ===\n\n&quot;)
</code></pre>
<pre><code>## === Longest Increasing Subsequence (Dynamic Programming) ===
</code></pre>
<pre><code class="language-r"># Test 1: Basic Example
nums1 &lt;- c(10, 9, 2, 5, 3, 7, 101, 18)
cat(&quot;Test 1: Basic Example\n&quot;)
</code></pre>
<pre><code>## Test 1: Basic Example
</code></pre>
<pre><code class="language-r">cat(&quot;Input Array:&quot;, paste(nums1, collapse = &quot;, &quot;), &quot;\n\n&quot;)
</code></pre>
<pre><code>## Input Array: 10, 9, 2, 5, 3, 7, 101, 18
</code></pre>
<pre><code class="language-r">result1 &lt;- longest_increasing_subsequence(nums1)
print_lis_dp(result1$dp_array, nums1)
</code></pre>
<pre><code>## DP Array for Longest Increasing Subsequence:
## Input Array: 10, 9, 2, 5, 3, 7, 101, 18 
## DP Array   : 1, 1, 1, 2, 2, 3, 4, 4 
## Max Length : 4
</code></pre>
<pre><code class="language-r">cat(&quot;Maximum Length:&quot;, result1$max_length, &quot;\n&quot;)
</code></pre>
<pre><code>## Maximum Length: 4
</code></pre>
<pre><code class="language-r">cat(&quot;One LIS Sequence:&quot;, paste(result1$lis_sequence, collapse = &quot;, &quot;), &quot;\n\n&quot;)
</code></pre>
<pre><code>## One LIS Sequence: 2, 3, 7, 18
</code></pre>
<pre><code class="language-r"># Test 2: Optimized Version
cat(&quot;Test 2: Optimized O(n log n) Version\n&quot;)
</code></pre>
<pre><code>## Test 2: Optimized O(n log n) Version
</code></pre>
<pre><code class="language-r">max_len_opt &lt;- longest_increasing_subsequence_optimized(nums1)
cat(&quot;Maximum Length (Optimized):&quot;, max_len_opt, &quot;\n&quot;)
</code></pre>
<pre><code>## Maximum Length (Optimized): 4
</code></pre>
<pre><code class="language-r">cat(&quot;Verification: Both methods match:&quot;, result1$max_length == max_len_opt, &quot;\n\n&quot;)
</code></pre>
<pre><code>## Verification: Both methods match: TRUE
</code></pre>
<pre><code class="language-r"># Test 3: All Possible LIS
cat(&quot;Test 3: All Possible LIS Sequences\n&quot;)
</code></pre>
<pre><code>## Test 3: All Possible LIS Sequences
</code></pre>
<pre><code class="language-r">all_lis &lt;- find_all_lis(nums1)
cat(&quot;Total number of LIS sequences:&quot;, length(all_lis), &quot;\n&quot;)
</code></pre>
<pre><code>## Total number of LIS sequences: 1
</code></pre>
<pre><code class="language-r">for (i in seq_along(all_lis)) {
  cat(&quot;LIS&quot;, i, &quot;:&quot;, paste(all_lis[[i]], collapse = &quot;, &quot;), &quot;\n&quot;)
}
</code></pre>
<pre><code>## LIS 1 : 2, 3, 7, 18
</code></pre>
<pre><code class="language-r">cat(&quot;\n&quot;)
</code></pre>
<pre><code class="language-r"># Test 4: Edge Cases
cat(&quot;Test 4: Edge Cases\n&quot;)
</code></pre>
<pre><code>## Test 4: Edge Cases
</code></pre>
<pre><code class="language-r">cat(&quot;Empty array:&quot;, longest_increasing_subsequence(c())$max_length, &quot;\n&quot;)
</code></pre>
<pre><code>## Empty array: 0
</code></pre>
<pre><code class="language-r">cat(&quot;Single element:&quot;, longest_increasing_subsequence(c(5))$max_length, &quot;\n&quot;)
</code></pre>
<pre><code>## Single element: 1
</code></pre>
<pre><code class="language-r">cat(&quot;All same elements:&quot;, longest_increasing_subsequence(c(3, 3, 3, 3))$max_length, &quot;\n&quot;)
</code></pre>
<pre><code>## All same elements: 1
</code></pre>
<pre><code class="language-r">cat(&quot;Strictly decreasing:&quot;, longest_increasing_subsequence(c(5, 4, 3, 2, 1))$max_length, &quot;\n&quot;)
</code></pre>
<pre><code>## Strictly decreasing: 1
</code></pre>
<pre><code class="language-r">cat(&quot;Strictly increasing:&quot;, longest_increasing_subsequence(c(1, 2, 3, 4, 5))$max_length, &quot;\n\n&quot;)
</code></pre>
<pre><code>## Strictly increasing: 5
</code></pre>
<pre><code class="language-r"># Test 5: Larger Dataset
cat(&quot;Test 5: Larger Dataset (n=20)\n&quot;)
</code></pre>
<pre><code>## Test 5: Larger Dataset (n=20)
</code></pre>
<pre><code class="language-r">set.seed(42)
nums_large &lt;- sample(1:100, 20)
cat(&quot;Input Array:&quot;, paste(nums_large, collapse = &quot;, &quot;), &quot;\n\n&quot;)
</code></pre>
<pre><code>## Input Array: 49, 65, 25, 74, 18, 100, 47, 24, 71, 89, 37, 20, 26, 3, 41, 27, 36, 5, 34, 87
</code></pre>
<pre><code class="language-r">result_large &lt;- longest_increasing_subsequence(nums_large)
cat(&quot;Maximum Length:&quot;, result_large$max_length, &quot;\n&quot;)
</code></pre>
<pre><code>## Maximum Length: 6
</code></pre>
<pre><code class="language-r">cat(&quot;One LIS Sequence:&quot;, paste(result_large$lis_sequence, collapse = &quot;, &quot;), &quot;\n\n&quot;)
</code></pre>
<pre><code>## One LIS Sequence: 18, 20, 26, 27, 34, 87
</code></pre>
<pre><code class="language-r"># Test 6: Performance Comparison
cat(&quot;Test 6: Performance Comparison (n=1000)\n&quot;)
</code></pre>
<pre><code>## Test 6: Performance Comparison (n=1000)
</code></pre>
<pre><code class="language-r">n &lt;- 1000
nums_perf &lt;- sample(1:1000, n)

start_time &lt;- Sys.time()
res_opt &lt;- longest_increasing_subsequence_optimized(nums_perf)
opt_time &lt;- as.numeric(Sys.time() - start_time, units = &quot;secs&quot;)

cat(&quot;Optimized O(n log n) result:&quot;, res_opt, &quot;\n&quot;)
</code></pre>
<pre><code>## Optimized O(n log n) result: 61
</code></pre>
<pre><code class="language-r">cat(&quot;Time taken:&quot;, sprintf(&quot;%.4f sec&quot;, opt_time), &quot;\n&quot;)
</code></pre>
<pre><code>## Time taken: 0.0189 sec
</code></pre>
<pre><code class="language-r"># Verify correctness with basic DP (smaller sample for time comparison)
nums_small &lt;- nums_perf[1:100]
start_time &lt;- Sys.time()
res_basic &lt;- longest_increasing_subsequence(nums_small)
basic_time &lt;- as.numeric(Sys.time() - start_time, units = &quot;secs&quot;)

cat(&quot;Basic O(n²) result (n=100):&quot;, res_basic$max_length, &quot;\n&quot;)
</code></pre>
<pre><code>## Basic O(n²) result (n=100): 18
</code></pre>
<pre><code class="language-r">cat(&quot;Time taken:&quot;, sprintf(&quot;%.4f sec&quot;, basic_time), &quot;\n&quot;)
</code></pre>
<pre><code>## Time taken: 0.0020 sec
</code></pre>
<pre><code class="language-r"># Test 7: Real-world Example - Stock Prices
cat(&quot;Test 7: Real-world Example - Stock Price Trend\n&quot;)
</code></pre>
<pre><code>## Test 7: Real-world Example - Stock Price Trend
</code></pre>
<pre><code class="language-r">stock_prices &lt;- c(100, 102, 98, 105, 103, 107, 110, 108, 112, 115, 113, 118, 120, 117, 125)
cat(&quot;Stock Prices:&quot;, paste(stock_prices, collapse = &quot;, &quot;), &quot;\n&quot;)
</code></pre>
<pre><code>## Stock Prices: 100, 102, 98, 105, 103, 107, 110, 108, 112, 115, 113, 118, 120, 117, 125
</code></pre>
<pre><code class="language-r">stock_result &lt;- longest_increasing_subsequence(stock_prices)
cat(&quot;Longest upward trend length:&quot;, stock_result$max_length, &quot;\n&quot;)
</code></pre>
<pre><code>## Longest upward trend length: 10
</code></pre>
<pre><code class="language-r">cat(&quot;Longest upward trend:&quot;, paste(stock_result$lis_sequence, collapse = &quot;, &quot;), &quot;\n&quot;)
</code></pre>
<pre><code>## Longest upward trend: 100, 102, 103, 107, 108, 112, 113, 118, 120, 125
</code></pre>
<pre><code class="language-r">cat(&quot;Percentage increase:&quot;, 
    sprintf(&quot;%.2f%%&quot;, (stock_result$lis_sequence[length(stock_result$lis_sequence)] / 
                      stock_result$lis_sequence[1] - 1) * 100), &quot;\n&quot;)
</code></pre>
<pre><code>## Percentage increase: 25.00%
</code></pre>
</div>
</body>
</html>
